////////////////////////////////////////////////////////////////////////////////
/*
//---readme---//
//skewHeap//
interfaces: 
1 createskewHeap: const vector<elemType> &dataBase;
2 destroyskewHeap: skewHeapNode *&root;
3 mergeskewHeap: skewHeapNode *&roota, skewHeapNode *&rootb;
4 insertskewHeapNode: skewHeapNode *&root, elemType &dt;
5 extractMinNode: skewHeapNode *&root.
*/
//made by HaoyuHu
//Tsinghua University
////////////////////////////////////////////////////////////////////////////////
typedef int elemType;
struct skewHeapNode {
	elemType data;
	skewHeapNode *lchild, *rchild;
	skewHeapNode(const elemType &val): data(val), lchild(NULL), rchild(NULL) {}
};

template <typename type>
void swapPtr(type &x, type &y) {
	type t = x;
	x = y; y = t;
}

skewHeapNode *createskewHeap(const vector<elemType> &vec);
void destroyskewHeap(skewHeapNode *&root);
skewHeapNode *mergeskewHeap(skewHeapNode *&roota, skewHeapNode *&rootb);
void insertskewHeapNode(skewHeapNode *&root, const elemType &dt);
skewHeapNode *extractMinNode(skewHeapNode *&root);

skewHeapNode *createskewHeap(const vector<elemType> &vec) {
	skewHeapNode *root = NULL;
	for (int i = 0; i != vec.size(); ++i)
		insertskewHeapNode(root, vec[i]);
	return root;
}
void destroyskewHeap(skewHeapNode *&root) {
	skewHeapNode *left = root->lchild, *right = root->rchild;
	delete(root); root = NULL;
	if (left) destroyskewHeap(left);
	if (right) destroyskewHeap(right);
}
skewHeapNode *mergeskewHeap(skewHeapNode *&roota, skewHeapNode *&rootb) {
	if (!roota || !rootb)
		return roota ? roota : rootb;
	if (roota->data > rootb->data)
		swapPtr<skewHeapNode*>(roota, rootb);
	roota->rchild = mergeskewHeap(roota->rchild, rootb);
	swapPtr(roota->lchild, rootb->rchild);
	return roota;
}
void insertskewHeapNode(skewHeapNode *&root, const elemType &dt) {
	skewHeapNode *cur = new skewHeapNode(dt);
	root = mergeskewHeap(root, cur);
}
skewHeapNode *extractMinNode(skewHeapNode *&root) {
	skewHeapNode *min = root;
	root = mergeskewHeap(root->lchild, root->rchild);
	return min;
}